package main

import "fmt"


/*
接雨水
给定 n 个非负整数表示每个宽度为 1 的柱子的高度图，计算按此排列的柱子，下雨之后能接多少雨水。

示例 1：
输入：height = [0,1,0,2,1,0,1,3,2,1,2,1]
输出：6

示例 2：
输入：height = [4,2,0,3,2,5]
输出：9
 */


func trap(height []int) (ans int) {
	res := 0
	// 双指针
	left, right := 0, len(height) - 1  // 指向左边界与右边界
	leftMax, rightMax := 0, 0   // 分别保存左右的最大高度
	max := func(x, y int) int {
		if x > y {
			return x
		}
		return y
	}
	for left < right {
		leftMax = max(leftMax, height[left])
		rightMax = max(rightMax, height[right])
		if leftMax < rightMax {
			res += leftMax - height[left]
			left ++
		}else {
			res += rightMax - height[right]
			right --
		}
	}


	return res
}


func main() {
	height := []int{4,2,0,3,2,5}
	fmt.Println(trap(height))
}
